package LeetCode;

//给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
public class TestNum234 {
    public boolean isPalindrome(ListNode head) {
        //先定义快慢节点找到中间节点
        ListNode fast = head;
        ListNode low = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            low = low.next;
        }
        //将中间节点以后的链表反转
        ListNode prev = reverseList(low);
        while (prev != null && head != null) {
            //分别从head节点和prev节点开始向下比较，如果不同则不是回文链表
            if (prev.val != head.val) {
                return false;
            }
            prev=prev.next;
            head=head.next;
        }
        return true;
    }

    //链表反转
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode sec = head.next;
        ListNode newHead = reverseList(sec);
        sec.next = head;
        head.next = null;
        return newHead;
    }
}
